package sort;

/**
 * 希尔排序
 *
 * @author or2
 * @date 2021/8/7 17:50
 */
public class Shell {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        int length = arr.length;

        int span = length >> 1;
        while (span >= 1) {

            /**
             * 可以简化为`两重循环`
             */
//            按 span 进行分组, 遍历所有分组进行排序
            for (int i = 0; i < span; i++) {
//                从当前分组的第二个开始插入排序
                for (int j = i + span; j < length; j += span) {
//                    从当前结点, 在分组内进行-插入排序
                    int p = j;
                    E temp = arr[p];
                    while (p - span >= 0) {
                        if (temp.compareTo(arr[p - span]) < 0) {
                            arr[p] = arr[p - span];
                            p -= span;
                        } else {
                            break;
                        }
                    }
                    arr[p] = temp;
                }
            }

            span >>= 1;
        }
    }
}
